Papers^γ / Sergey Kirgizov

### Style I like the Levin style, he writes a bit provocative phrases that looks, in the same time, incredibly truthful (at least for the author himself). Consider for example what he says about the invention of positional numeral systems and Quantum computers: > Archimedes made a great discovery that digital representation of numbers is exponentially > more efficient than analog ones (sand pile sizes). Many subsequent analog devices yielded > unimpressive results. It is not clear why QCs [quantum computers] should be an exception. ### One-way function and the axiom of choice One-way functions and the axiom of choice deals with practical or conceptual (im-)possibility to solve [inverse problems](https://en.wikipedia.org/wiki/Inverse_problem) arising in Computer Science and Mathematics. ### Kolmogorov complexity and One-way functions Two primes $p$ and $q$ have almost the same [informational content](https://en.wikipedia.org/wiki/Algorithmic_information_theory) as their product $pq$. However, the [$p, q \mapsto pq$](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Arithmetic_functions) is much more easy to do than [$pq \mapsto p,q$](https://en.wikipedia.org/wiki/Integer_factorization#Prime_decomposition).

Arxiv link: https://arxiv.org/abs/1807.06874

This a nice paper and I think you manage to keep your article easily readable. Specially the figures, such as figure 3, helped me follow your explanations. I haven't finished reading the paper but I have minor remarks/typo: - Page 9 in the definition of multigraph, should e(v, V) be transformed to e({v},V) in order to be completely rigorous? - I don't know what “maximum-entropy sampling” is but why quoting it ? - I don't get the use of Reversible Decompression, apart from being an extreme case of external information. I don't think this case deserve to be explained in detailed, as it does not have any impact on the understanding of the paper. - I find the notation for definition 10 a bit confusing. A Cartesian MultiEdge Partition is made of Cartesian products of two vertex subsets. The notation for each cartesian product uses subscript on vertex subset: $(V_i \times V'_i)$ for the $i$th product. This lead me to think that $(V_i \times V'_i)$ was a possible Cartesian product. This also lead me to think that Cartesian MultiEdge Partition are made of Cartesian product of vertex partition: $B(V \times V) = \{(V_i \times V_j)\}\ \forall V_i \in P_1, V_j \in P_2 \wedge P_1 \in B(V), P_2 \in B(V)$. I think all Cartesian product of vertex partition are Cartesian MultiEdge partition. Is there any Cartesian MultiEdge Partition that is not a Cartesian product of vertex partition? - In the conplete case after definition 11, I don't know the notation $\omega$ for the number of feasible partitions. - I think you missed a $\lambda$ in the lagrange function page 21. Should it be $q_{\lambda}(VVT)= |VVT| + \lambda Loss(VVT)$

One of my favorite papers. Related to [Axioms for centrality](https://papers-gamma.link/paper/54)